<?php
/**
 * User: helloJiu
 * Date: 2021/9/24
 * Time: 13:49
 */

namespace App\Algorithm\DP;


use App\Util\PrintUtil;

class Coin
{
    private $cnt = 0;

    private $coins = [];
    /**
     * @param $n 给定 1  5 10 25 面值的硬币, 求凑够n所需要的最小硬币
     * @return int|mixed
     */
    public function coin1($n){
        if($n<1){
            return PHP_INT_MAX;
        }
        if($n == 1 || $n == 5 || $n== 10 || $n == 25){
            return 1;
        }

        // 每次选
        return min(
            $this->coin1($n-1),
            $this->coin1($n-5),
            $this->coin1($n-10),
            $this->coin1($n-25),
        ) + 1;
    }

    /**
     * 自顶向下
     * @param $n
     * @return mixed
     */
    public function coin2($n){
        $dp = [];
        for($i=0; $i<=$n; $i++){
            $dp[$i] = 0;
        }
        $dp[1] = $dp[5] = $dp[10] = $dp[25] = 1;
        $this->coin2Internal($n, $dp);
        PrintUtil::println($dp);
        PrintUtil::println("cnt: " . $this->cnt);
        return $dp[$n];
    }

    public function coin2Internal($n, &$dp){
        $this->cnt++;
        if($n<1){
            return PHP_INT_MAX;
        }

        if(!empty($dp[$n-1])){
            $min1 = $dp[$n-1];
        }else{
            $min1 = $this->coin2Internal($n-1, $dp);
        }


        if(!empty($dp[$n-5])){
            $min5 = $dp[$n-5];
        }else{
            $min5 = $this->coin2Internal($n-5, $dp);
        }

        if(!empty($dp[$n-10])){
            $min10 = $dp[$n-10];
        }else{
            $min10 = $this->coin2Internal($n-10, $dp);
        }

        if(!empty($dp[$n-25])){
            $min25 = $dp[$n-25];
        }else{
            $min25 = $this->coin2Internal($n-25, $dp);
        }

        // 每次选
        $dp[$n] = min($min1, $min5, $min10, $min25) + 1;

        return $dp[$n];
    }

    /**
     * 自底向上
     * @param $n
     */
    public function coin3($n){
        $dp = [];
        for($i=0; $i<=$n; $i++){
            $dp[$i] = 0;
        }
        $dp[1] = $dp[5] = $dp[10] = $dp[25] = 1;
        for($i=1; $i<=$n; $i++){
            if ($i<5){
                $dp[$i] = $dp[$i-1] + 1;
                $this->coins[] = 1;
            }elseif($i < 10){
                $dp[$i] = $dp[$i-5] + 1;
                $this->coins[] = 5;
            }elseif($i < 25){
                $dp[$i] = $dp[$i-10] + 1;
                $this->coins[] = 10;
            }else{
                $dp[$i] = $dp[$i-25] + 1;
                $this->coins[] = 25;
            }
        }
        PrintUtil::println($this->coins);
        return $dp[$n];

    }
}